package org.acegisecurity.util.expressioncompiler;

import java.util.StringTokenizer;

import org.acegisecurity.Authentication;
import org.acegisecurity.util.ExpressionEvaluator;
import org.acegisecurity.util.IllegalExpressionException;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * <p>
 * This class takes care of the compilation of a logical (conditional)
 * expression
 * </p>
 * <p>
 * Expressions may contain the keywords (reserved words): AND, OR and NOT (case
 * insensitive) <br/> Delimiters are: " " (space), "(" and ")" <br/>
 * </p>
 * <p>
 * The internal Tokenizer class functions as the lexer for this compiler. The
 * lexicon is very straight forward. We need the words and the ")" and "("
 * tokens. Whitespace can be ignored. Based on these tokens the expression can be
 * compiled.
 * </p>
 * <p>
 * This class does not need to be instantiated to make it work.<br/>
 * Example:
 * </p>
 * <pre>
 * String expr = &quot;ROLE_ADMIN or (ROLE_EIGENAAR or ROLE_BEHEERDER)&quot;;
 * LogicalExpressionCompiler.CompiledExpression compiledExpression = LogicalExpressionCompiler.compile(expr);
 * //... when the Authentication object is available on can call 
 * compiledExpression.matches(authenticationObject);
 * //... or if the compiled expression may be discarded after evaluation:
 * LogicalExpressionCompiler.parse(expr).matches(authenticationObject);
 * </pre>
 * 
 * <p>
 * Because it is not a complete compiler it assumes that all expressions given
 * to it are correct. This means that the compiler does not check the grammar /
 * syntax of the expression. When e.g. an expression looks like <b>ROLE_A and</b>
 * the compiler will accept this. The moment the matches method is called though
 * a NullPointerException is thrown because there is no "right" side of the
 * expression and an AND expression expects this right side.
 * </p>
 * <p>
 * NOTE: Because the (@link LogicalExpressionCompiler} pre-compiles the whole
 * expression a possible optimization is possible. Compiled expressions can be
 * saved for the next time they are needed. Compilation of an expression is
 * (relatively) the most expensive part of the process. 
 * </p> 
 * 
 * @author Ivo Woltring
 */
public class LogicalExpressionCompiler implements ExpressionEvaluator {
	private static final Log logger = LogFactory.getLog(LogicalExpressionCompiler.class);

	/**
	 * The class that implements this interface demands a {@link Authentication}
	 * object as input
	 */
	public interface CompiledExpression {
		boolean matches(Authentication authentication);
	}

	/**
	 * This static method compiles the given expression
	 * 
	 * @param expression
	 *            to be compiled
	 * @return CompiledExpression containing the whole expression tree
	 */
	public static CompiledExpression parse(String expression) {
		return new Compiler(new Tokenizer(expression)).parse();
	}

	/**
	 * It extents the StringTokenizer and instantiates it with the needed
	 * delimiters and tells the StringTokenizer to return the delimiters as
	 * tokens. We need the delimiters as tokens because otherwise it is not
	 * possible to determine which expression belongs to which part in the
	 * expression.
	 * 
	 * This version of nextToken (overridden) returns all relevant tokens.
	 * Whitespace is eaten.
	 * 
	 * @author Ivo Woltring
	 * @author Jamie Craane
	 */
	static class Tokenizer extends StringTokenizer {
		Tokenizer(String expression) {
			super(expression, " ()", true);
		}
		
		/*
		 * (non-Javadoc)
		 * @see java.util.StringTokenizer#nextToken()
		 */
		public String nextToken() {
			while (super.hasMoreTokens()) {
				final String token = super.nextToken().trim();
				if (token.length() > 0) {
					return token;
				}
			}
			return null;
		}
	}

	/**
	 * The Compiler class does the real evaluation of the expression. It needs a
	 * Tokenizer as input. It builds an expression tree.
	 * 
	 * @author Ivo Woltring
	 */
	static class Compiler {
		private static final String AND_OPERATOR = "and";
		private static final String OR_OPERATOR = "or";
		private static final String NOT_OPERATOR = "not";
		private static final String LPAREN = "(";
		private static final String RPAREN = ")";
		final Tokenizer tokenizer;

		/**
		 * The constructor
		 * 
		 * @param tokenizer
		 *            (the lexer of this compiler)
		 */
		public Compiler(Tokenizer tokenizer) {
			this.tokenizer = tokenizer;
		}

		/**
		 * The compile method is called to compile the expression into an
		 * expression tree
		 * 
		 * @return CompiledExpression
		 */
		public CompiledExpression parse() {
			return compile(compile(null));
		}

		/**
		 * This method builds recursively the expression tree
		 * 
		 * @param left the left side of the expression
		 * @return CompiledExpression
		 */
		CompiledExpression compile(final CompiledExpression left) {
			final String token = tokenizer.nextToken();
			if (token == null) {
				return left;
			}
			abstract class NextExpression implements CompiledExpression {
				CompiledExpression right;

				NextExpression(CompiledExpression right) {
					this.right = right;
				}
			}
			if (token.equalsIgnoreCase(NOT_OPERATOR)) {
				if (logger.isDebugEnabled()) {
					logger.debug("Compiling: [NOT_OPERATOR]");
				}
				return compile(new NextExpression(compile(null)) {
					public boolean matches(Authentication authentication) {
						final boolean rht = right.matches(authentication);
						if (logger.isDebugEnabled()) {
							logger.debug("Evaluated NOT [" + rht + "] to [" + (!rht) + "]");
						}
						return !rht;
					}
				});
			}
			if (token.equalsIgnoreCase(OR_OPERATOR)) {
				if (logger.isDebugEnabled()) {
					logger.debug("Compiling: [OR_OPERATOR]");
				}
				return new NextExpression(compile(compile(null))) {
					public boolean matches(Authentication authentication) {
						final boolean lft = left.matches(authentication);
						final boolean rht = right.matches(authentication);
						if (logger.isDebugEnabled()) {
							logger.debug("Evaluated [" + lft + "] OR [" + rht + "] to [" + (lft || rht) + "]");
						}
						return lft || rht;
					}
				};
			}
			if (token.equalsIgnoreCase(AND_OPERATOR)) {
				if (logger.isDebugEnabled()) {
					logger.debug("Compiling: [AND_OPERATOR]");
				}
				return compile(new NextExpression(compile(null)) {
					public boolean matches(Authentication authentication) {
						final boolean lft = left.matches(authentication);
						final boolean rht = right.matches(authentication);
						if (logger.isDebugEnabled()) {
							logger.debug("Evaluated [" + lft + "] AND [" + rht + "] to [" + (lft && rht) + "]");
						}
						return lft && rht;
					}
				});
			}
			if (token.equals(LPAREN)) {
				if (logger.isDebugEnabled()) {
					logger.debug("Compiling: [LPAREN]");
				}
				return compile(new NextExpression(compile(null)) {
					public boolean matches(Authentication authentication) {
						final boolean rht = right.matches(authentication);
						if (logger.isDebugEnabled()) {
							logger.debug("Evaluated braced expression to [" + rht + "]" );
						}
						return right.matches(authentication);
					}
				});
			}
			if (token.equals(RPAREN)) {
				if (logger.isDebugEnabled()) {
					logger.debug("Compiling: [RPAREN]");
				}
				return left;
			}
			// Atomic part of an expression
			if (logger.isDebugEnabled()) {
				logger.debug("Compiling: ["+token+"]");
			}
			return new CompiledExpression() {
				public boolean matches(Authentication authentication) {
					final String[] roles = getRoles(authentication);
					for (int i = 0; i < roles.length; i++) {
						if (token.equals(roles[i])) {
							if (logger.isDebugEnabled()) {
								logger.debug("Evaluated [" + token + "] to [true]");
							}
							return true;
						}
					}
					if (logger.isDebugEnabled()) {
						logger.debug("Evaluated [" + token + "] to [false]");
					}
					return false;
				}
			};
		}
	}

	/**
	 * Returns the roles for the authentication as a String[]
	 * @param authentication The authentication to extract the roles from.
	 * @return The roles as a String[]
	 */
	private static String[] getRoles(Authentication authentication) {
		final String[] roles = new String[authentication.getAuthorities().length];
		for (int i = 0; i < authentication.getAuthorities().length; i++) {
			roles[i] = authentication.getAuthorities()[i].getAuthority();
		}
		return roles;
	}
	/*
	 * (non-Javadoc)
	 * @see org.acegisecurity.util.ExpressionEvaluator#match(java.lang.String, org.acegisecurity.Authentication)
	 */
	public boolean match(String expr, Authentication authentication) throws IllegalExpressionException {
		try {
			return LogicalExpressionCompiler.parse(expr).matches(authentication);
		} catch (final Throwable t) {
			throw new IllegalExpressionException("Error occurred during the evaluation of the following expression: [" + expr + "].");
		}
	}

}
